package com.base.dp;

import java.util.Arrays;

/**
 * 给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
 * <p>
 * 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的
 * 子序列
 * 。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [10,9,2,5,3,7,101,18]
 * 输出：4
 * 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
 * 示例 2：
 * <p>
 * 输入：nums = [0,1,0,3,2,3]
 * 输出：4
 * 示例 3：
 * <p>
 * 输入：nums = [7,7,7,7,7,7,7]
 * 输出：1
 */
public class LengthOfLIS {
    public static void main(String[] args) {
        LengthOfLIS length = new LengthOfLIS();
        System.out.println(length.lengthOfLIS3(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));
    }

    public int lengthOfLIS(int[] nums) {
       // 定义 dp[i] 为以 nums[i] 结尾的最长严格递增子序列的长度。
        // 对于每一个 i（从 0 到 nums.length - 1），
        // 我们需要考虑所有 j（从 0 到 i - 1）的情况，
        // 找出能够形成递增序列的 dp[j] 的最大值，然后 dp[i] = dp[j] + 1。
        if (nums == null || nums.length == 0) return 0;

        int[] dp = new int[nums.length];
        int maxLen = 1;
        Arrays.fill(dp, 1); // 初始化dp数组
        //从第二个开始算，当前元素能否加到前面元素的子序列之后，然后更新子序列
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    //dp[i]能否加到dp[j]所表示子序列的后面形成新的子序列，
                    // 更新最长的子序列
                    //
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxLen = Math.max(maxLen, dp[i]); // 更新最长长度
        }

        return maxLen;
    }
    public int lengthOfLIS3(int[] nums) {
        int[] dp = new int[nums.length]; // dp数组用于存储LIS的潜在候选序列
        int len = 0; // len表示当前dp数组中实际存储的有效序列长度
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num); // 在dp数组的前len个元素中二分查找num
            if (i < 0) {
                i = -(i + 1); // 如果num不在dp数组中，则i为num应该插入的位置的负数减1
            }
            dp[i] = num; // 将num放置在dp数组的正确位置上
            if (i == len) { // 如果num放置在dp数组的末尾，则意味着找到了一个更长的递增子序列
                len++; // 因此，我们需要增加dp数组的有效长度
            }
        }
        return len; // 最后，len即为最长递增子序列的长度
    }
    public int lengthOfLIS2(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return 1;
        }
        //定义dp[i][j] 是从下标i开始到下标j结束，最长严格递增子序列
        int[] dp = new int[length];

        int allMax = 0;
        int result = 0;
        for (int i = 0; i < length - 1; i++) {
            //当前子序列中最大的数
            int max = nums[i];
            int index = i;
            dp[index] = 1;
            for (int j = i + 1; j < length; j++) {
                if (nums[j] > max) {
                    dp[j] = dp[index] + 1;
                    max = nums[j];
                    index = j;
                    result = index;
                }
            }
            if (dp[result]>allMax){
                allMax = dp[result];
            }
        }

        return allMax;
    }
}
